/**
 * Copyright (C) 2008+ Spark Zheng
 *
 * @file	src/heap.c
 * @brief 
 *      Heap module, A basic datastruct module.
 *      Simple heap and merged-heap datastructures
 *
 * @see		dlib
 * @module      dlib
 *
 * @history
 *      version 0.1.0, spark init heap module with min heap 
 */

#include "heap.h"
#include "list.h"
#include "mempool.h"

static inline void _simple_heap_adjust_up(sheap_t *heap, uint32_t from, void *data);
static inline void _simple_heap_adjust_down(sheap_t *heap, uint32_t from, void *data);
static inline int _simple_heap_expand(sheap_t *heap, uint32_t new_capacity);

static inline void _simple_heap_adjust_up(sheap_t *heap, uint32_t from, void *data)
{
	uint32_t parent = (from - 1) / 2;

	while (from && (*(heap->heap_compare))(heap->heap_nodes[parent].heap_data, data) > 0) {
		heap->heap_nodes[from].heap_data = heap->heap_nodes[parent].heap_data;
		from = parent;
		parent = (from - 1) / 2;
	}

	heap->heap_nodes[from].heap_data = data;
	return;
}

static inline void _simple_heap_adjust_down(sheap_t *heap, uint32_t from, void *data)
{
	uint32_t rchild = 2 * (from + 1);

	while (rchild <= heap->heap_current) {
		rchild -= rchild == heap->heap_current ||
			  ((*(heap->heap_compare))(heap->heap_nodes[rchild].heap_data,
					  heap->heap_nodes[rchild - 1].heap_data) > 0);

		if ((*(heap->heap_compare))(data, heap->heap_nodes[rchild].heap_data) < 0)
			break;

		heap->heap_nodes[from].heap_data = heap->heap_nodes[rchild].heap_data;

		from = rchild;
		rchild = 2 * (from + 1);
	}
	
	_simple_heap_adjust_up(heap, from, data);
	return;
}

static inline int _simple_heap_expand(sheap_t *heap, uint32_t new_capacity)
{
	sheap_node_t *heap_nodes = NULL;

	if (new_capacity <= heap->heap_capacity) {
		return -1;
	}

	heap_nodes = drealloc_nb(heap->heap_nodes, new_capacity * sizeof(sheap_node_t));
	if (heap_nodes == NULL) {
		return -2;
	}

	heap->heap_nodes = heap_nodes;
	heap->heap_capacity = new_capacity;

	return 0;
}

sheap_t *simple_heap_init(uint32_t capacity, heap_compare_fn compare_cb,
		heap_relval_fn relval_cb)
{
	sheap_t *heap = NULL;
	
	if (capacity == 0 || compare_cb == NULL) {
		return NULL;
	}

	heap = (sheap_t *)dmalloc(sizeof(*heap));

	dlib_lock_init(&heap->heap_lock);

	heap->heap_nodes = dmalloc(capacity * sizeof(sheap_node_t));
	heap->heap_capacity = capacity;
	heap->heap_current = 0;
	heap->heap_compare = compare_cb;
	heap->heap_relval = relval_cb;

	return heap;
}

void simple_heap_exit(sheap_t *heap)
{
	uint32_t i;

	if (heap == NULL) {
		return;
	}

	dlib_lock_lock(&heap->heap_lock);
	if (heap->heap_nodes != NULL) {
		for (i = 0; i < heap->heap_current; i++) {
			if (heap->heap_relval != NULL)
				(*(heap->heap_relval))(heap->heap_nodes[i].heap_data);
		}
		dfree(heap->heap_nodes);
		heap->heap_nodes = NULL;
	}
	dlib_lock_unlock(&heap->heap_lock);
	dlib_lock_exit(&heap->heap_lock);

	dfree(heap);
	heap = NULL;

	return;
}

int simple_heap_push(sheap_t *heap, void *data)
{
	int ret = 0;
	sheap_node_t *heap_node;

	if (heap == NULL) {
		return -1;
	}

	dlib_lock_lock(&heap->heap_lock);
	if (heap->heap_current == heap->heap_capacity) {
		ret = _simple_heap_expand(heap, heap->heap_capacity + SIMPLE_HEAP_EXPANDER);
		if (ret < 0) {
			dlib_lock_unlock(&heap->heap_lock);
			return ret;
		}
	} 

	heap_node = &(heap->heap_nodes[heap->heap_current]);
	heap_node->heap_index = heap->heap_current;
	heap_node->heap_data = data;

	heap->heap_current++;

	_simple_heap_adjust_up(heap, heap_node->heap_index, heap_node->heap_data);
	dlib_lock_unlock(&heap->heap_lock);

	return ret;
}

int simple_heap_pop(sheap_t *heap, void **data_ptr)
{
	int ret = 0;

	if (heap == NULL || *data_ptr != NULL) {
		return -1;
	}

	dlib_lock_lock(&heap->heap_lock);
	if (heap->heap_current > 0) {
		*data_ptr = heap->heap_nodes[0].heap_data;
		heap->heap_nodes[0].heap_data = heap->heap_nodes[heap->heap_current - 1].heap_data;
		heap->heap_current--;

		_simple_heap_adjust_down(heap, 0U, heap->heap_nodes[0].heap_data);

		ret = heap->heap_current;
	}
	dlib_lock_unlock(&heap->heap_lock);

	return ret;
}

int simple_heap_delete(sheap_t *heap, sheap_node_t *heap_node)
{
	if (heap == NULL || heap_node == NULL) {
		return -1;
	}

	dlib_lock_lock(&heap->heap_lock);
	heap_node->heap_data = heap->heap_nodes[heap->heap_current - 1].heap_data;
	_simple_heap_adjust_down(heap, heap_node->heap_index, heap_node->heap_data);
	heap->heap_current--;
	dlib_lock_unlock(&heap->heap_lock);

	return 0;
}

int simple_heap_extract(sheap_t *heap)
{
	UNUSED_PARAM(heap);
	return 0;
}

int simple_heap_change(sheap_t *heap, void *old_data, void *new_data)
{
	UNUSED_PARAM(heap);
	UNUSED_PARAM(old_data);
	UNUSED_PARAM(new_data);
	return 0;
}

int simple_heap_sort(sheap_t *heap, void **array, size_t array_len)
{
	int ret;
	uint32_t i;

	if (heap == NULL || array == NULL || array_len <= 0) {
		return -1;
	}

	for (i = 0; 0 < heap->heap_current && i < array_len; i++) {
		array[i] = NULL;
		ret = simple_heap_pop(heap, &array[i]);
		if (ret < 0) {
			return ret;
		}
	}

	return i;
}

void simple_heap_dump(sheap_t *heap, heap_dumpout_fn dump_cb)
{
	uint32_t i;

	if (heap == NULL) {
		return;
	}

	dlib_lock_lock(&heap->heap_lock);
	fprintf(stdout, "HEAP simple_heap dump out:\n");
	fprintf(stdout, "    capacity is %u.\n", heap->heap_capacity);
	fprintf(stdout, "    current node_nr is %d.\n", heap->heap_current);
	fprintf(stdout, "    heap nodes data:\n");
	for (i = 0; i < heap->heap_current; i++) {
		if (dump_cb != NULL) {
			(*dump_cb)(heap->heap_nodes[i].heap_data);
		}
	}
	fprintf(stdout, "\n");
	dlib_lock_unlock(&heap->heap_lock);

	return;
}
